package org.yao.datastructure.linkedlist;

/**
 * @author Henry Yao
 * @since
 */
public class SingleLinkedListDemo {
    public static void main(String[] args) {
        SingleLinkedList singleLinkedList = new SingleLinkedList();
//        testAdd(singleLinkedList);
        singleLinkedList.addByRank(new HeroNode(2, "甄姬"));
        singleLinkedList.addByRank(new HeroNode(1, "后裔"));
        singleLinkedList.addByRank(new HeroNode(4, "荆轲"));
        singleLinkedList.addByRank(new HeroNode(3, "虞姬"));
        singleLinkedList.addByRank(new HeroNode(1, "后裔"));
//        singleLinkedList.show();
//        System.out.println("有效节点数为" + singleLinkedList.countNode());
//        HeroNode lastIndexNode = singleLinkedList.findLastIndexNode(2);
//        System.out.printf("倒数%d个节点为%s\n", 2, lastIndexNode.toString());
//        SingleLinkedList list = singleLinkedList.reverseList(singleLinkedList);
//        System.out.println("反转后的链表为：");
//        list.show();
//        singleLinkedList.delNode(3);
//        singleLinkedList.show();
//        singleLinkedList.delNode(5);
//        singleLinkedList.show();
        singleLinkedList.updateNode(new HeroNode(3, "小青龙"));
        singleLinkedList.show();
        singleLinkedList.updateNode(new HeroNode(5, "小青龙"));
        singleLinkedList.show();

    }

    private static void testAdd(SingleLinkedList singleLinkedList) {
        singleLinkedList.add(new HeroNode(1, "后裔"));
        singleLinkedList.add(new HeroNode(2, "甄姬"));
        singleLinkedList.add(new HeroNode(3, "虞姬"));
        singleLinkedList.show();
    }
}


class SingleLinkedList {
    /**
     * 头节点引用
     */
    private HeroNode head;

    public SingleLinkedList() {
        head = new HeroNode(0, "");
    }

    /**
     * 增加一个节点
     *
     * @param node
     */
    public void add(HeroNode node) {
        HeroNode temp = head;
        while (temp.getNext() != null) {
            temp = temp.getNext();
        }
        temp.setNext(node);
    }

    /**
     * 打印所有节点
     */
    public void show() {
        HeroNode temp = head;
        while (temp.getNext() != null) {
            System.out.println(temp.getNext());
            temp = temp.getNext();
        }
    }

    /**
     * 根据排名插入，如果已存在则提示
     */
    public void addByRank(HeroNode node) {
        // 从头节点开始遍历
        HeroNode temp = head;
        while (temp.getNext() != null) {
            // 判断是否已存在
            if (temp.getNext().getRank() == node.getRank()) {
                System.out.printf("排名为%d的英雄已存在\n", node.getRank());
                return;
            }
            // 插入节点排名小于下一个节点的排名 则插入
            if (temp.getNext().getRank() > node.getRank()) {
                // 将插入节点的next执行temp的下一个节点，这一步一定要在前面 否则会循环引用
                node.setNext(temp.getNext());
                // 将temp的next指向插入节点
                temp.setNext(node);
                return;
            }
            temp = temp.getNext();
        }
        // 遍历没找到就放大temp后面
        temp.setNext(node);
    }

    /**
     * 计算有效节点个数
     */
    public int countNode() {
        if (head.getNext() == null) {
            return 0;
        }
        int count = 0;
        HeroNode temp = head;
        while (temp.getNext() != null) {
            count++;
            temp = temp.getNext();
        }
        return count;
    }

    /**
     * 找到链表中倒数第K个节点
     *
     * @param k 倒数
     * @return
     */
    public HeroNode findLastIndexNode(int k) {
        // 判断链表是否为空
        if (head.getNext() == null) {
            System.out.println("链表为空");
            return null;
        }
        // 判断k和有效节点数大小
        int length = countNode();
        if (k > length) {
            System.out.println("输入数字无效");
            return null;
        }
        // 倒数第k个节点，相当于从头节点往后移length-k次
        HeroNode temp = head;
        for (int i = 0; i < length - k + 1; i++) {
            temp = temp.getNext();
        }
        return temp;
    }

    /**
     * 将单链表反转
     * h->1->3->4  =>  h->4->3->1
     *
     * @param list
     * @return
     */
    public SingleLinkedList reverseList(SingleLinkedList list) {
        //判断链表有效节点是不是大于1，小于等于1无需反转
        if (countNode() <= 1) {
            return list;
        }
        // 创建新的备用头节点
        HeroNode newHead = new HeroNode(0, "备用");
        //创建一个新的链表
        SingleLinkedList newList = new SingleLinkedList();
        newList.add(newHead);
        // 遍历原链表，将每个节点插入到新链表的头节点后面
        HeroNode temp = head.getNext();
        HeroNode next = null;
        while (true) {
            // 保存当前遍历节点的下一个节点，不然等setNext之后就会找不到了
            next = temp.getNext();
            // 1.temp节点的next指向新头节点的下一个节点,单链表插入一定要先连接后面
            temp.setNext(newHead.getNext());
            // 2.将新头节点的next指向temp节点
            newHead.setNext(temp);
            temp = next;
            if (temp == null) {
                break;
            }
        }
        // 将原链表头节点替换新链表头节点
        head.setNext(newHead.getNext());
        return list;
    }

    /**
     * 删除一个节点
     *
     * @param rank
     */
    public void delNode(int rank) {
        // 判断是否为空
        if (head.getNext() == null) {
            System.out.println("链表为空！");
        }
        // 删除标记
        boolean flag = false;
        // 删除单向链表的节点需要借助前一个节点
        HeroNode temp = head;
        while (temp.getNext() != null) {
            if (temp.getNext().getRank() == rank) {
                // temp节点的next指向当前节点的下一个节点
                temp.setNext(temp.getNext().getNext());
                flag = true;
            }
            temp = temp.getNext();
        }
        if (!flag) {
            System.out.println("未找到对应节点！");
        } else {
            System.out.println("删除成功");
        }

    }

    /**
     * 更新一个节点
     *
     * @param node
     */
    public void updateNode(HeroNode node) {
        // 判断是否为空
        if (head.getNext() == null) {
            System.out.println("链表为空！");
        }
        // 更新标记
        boolean flag = false;
        // 删除单向链表的节点需要借助前一个节点
        HeroNode temp = head;
        while (temp.getNext() != null) {
            if (temp.getNext().getRank() == node.getRank()) {
                // 新节点的next节点指向temp节点的next的next
                node.setNext(temp.getNext().getNext());
                // temp节点的next指向当前节点的下一个节点
                temp.setNext(node);
                flag = true;
            }
            temp = temp.getNext();
        }
        if (!flag) {
            System.out.println("未找到对应节点！");
        } else {
            System.out.println("更新成功");
        }

    }

}

class HeroNode {
    private int rank;
    private String name;
    private HeroNode next;

    public HeroNode(int rank, String name) {
        this.rank = rank;
        this.name = name;
    }

    public HeroNode getNext() {
        return next;
    }

    public void setNext(HeroNode next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "rank=" + rank +
                ", name='" + name + '\'' +
                '}';
    }

    public int getRank() {
        return rank;
    }

    public void setRank(int rank) {
        this.rank = rank;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }
}